1382D - Unmerge - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

#define pb push_back
#define me memset

int t;
int n;
int a[N];
vector<int> v;
int dp[N];

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        me(dp, 0, sizeof(dp));
        v.clear();
        for (int i = 1; i <= 2 * n; ++i) {
            scanf("%d", &a[i]);
        }
        int mx = a[1];
        int pos = 1;
        for (int i = 2; i <= 2 * n; ++i) {
            if (a[i] > mx) {
                v.pb(i - pos);
                mx = a[i];
                pos = i;
            }
        }

        v.pb(2 * n + 1 - pos);
        dp[0] = 1;
        for (int i = 0; i < (int)v.size(); ++i) {
            for (int j = n; j >= v[i]; --j) {
                dp[j] += dp[j - v[i]];
            }
        }
        if (dp[n]) puts("YES");
        else puts("NO");

    }

    return 0;
}